/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.tom_roush.pdfbox.util;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Map implementation with a smallest possible memory usage.
 * It should only be used for maps with small number of items
 * (e.g. &lt;30) since most operations have an O(n) complexity.
 * Thus it should be used in cases with large number of map
 * objects, each having only few items.
 *
 * <p><code>null</code> is not supported for keys or values.</p>
 */
public class SmallMap<K, V> implements Map<K, V>
{
   /**
    * stores key-value pair as 2 objects; key first; in case of empty map this might be <code>null</code>
    */
   private Object[] mapArr;

   /** Creates empty map. */
   public SmallMap()
   {
   }

   /** Creates map filled with entries from provided map. */
   public SmallMap(Map<? extends K, ? extends V> initMap)
   {
      putAll(initMap);
   }

   /**
    * Returns index of key within map-array or <code>-1</code>
    * if key is not found (or key is <code>null</code>).
    */
   private int findKey(Object key)
   {
      if (isEmpty() || (key==null))
      {
         return -1;
      }

      for ( int aIdx = 0; aIdx < mapArr.length; aIdx+=2 )
      {
         if (key.equals(mapArr[aIdx]))
         {
            return aIdx;
         }
      }

      return -1;
   }

   /**
    * Returns index of value within map-array or <code>-1</code>
    * if value is not found (or value is <code>null</code>).
    */
   private int findValue(Object value)
   {
      if (isEmpty() || (value==null))
      {
         return -1;
      }

      for ( int aIdx = 1; aIdx < mapArr.length; aIdx+=2 )
      {
         if (value.equals(mapArr[aIdx]))
         {
            return aIdx;
         }
      }

      return -1;
   }

   @Override
   public int size()
   {
      return mapArr == null ? 0 : mapArr.length >> 1;
   }

   @Override
   public boolean isEmpty()
   {
      return (mapArr == null) || (mapArr.length == 0);
   }

   @Override
   public boolean containsKey(Object key)
   {
      return findKey(key) >= 0;
   }

   @Override
   public boolean containsValue(Object value)
   {
      return findValue(value) >= 0;
   }

   @SuppressWarnings("unchecked")
   @Override
   public V get(Object key)
   {
      int kIdx = findKey(key);

      return kIdx < 0 ? null : (V) mapArr[kIdx+1];
   }

   @Override
   public V put(K key, V value)
   {
      if ((key == null) || (value == null))
      {
         throw new NullPointerException( "Key or value must not be null.");
      }

      if (mapArr == null)
      {
         mapArr = new Object[] { key, value };
         return null;
      }
      else
      {
         int kIdx = findKey(key);

         if (kIdx < 0)
         {
            // key unknown
            int oldLen = mapArr.length;
            Object[] newMapArr = new Object[oldLen+2];
            System.arraycopy(mapArr, 0, newMapArr, 0, oldLen);
            newMapArr[oldLen] = key;
            newMapArr[oldLen+1] = value;
            mapArr = newMapArr;
            return null;
         }
         else
         {
            // key exists; replace value
            @SuppressWarnings("unchecked")
            V oldValue = (V) mapArr[kIdx+1];
            mapArr[kIdx+1] = value;
            return oldValue;
         }
      }
   }

   @Override
   public V remove(Object key)
   {
      int kIdx = findKey(key);

      if (kIdx < 0)
      {
         // not found
         return null;
      }

      @SuppressWarnings("unchecked")
      V oldValue = (V) mapArr[kIdx+1];
      int oldLen = mapArr.length;

      if (oldLen == 2)
      {
         // was last entry
         mapArr = null;
      }
      else
      {
         Object[] newMapArr = new Object[oldLen-2];
         System.arraycopy(mapArr, 0, newMapArr, 0, kIdx);
         System.arraycopy(mapArr, kIdx+2, newMapArr, kIdx, oldLen - kIdx - 2);
         mapArr = newMapArr;
      }

      return oldValue;
   }

   @Override
   public final void putAll(Map<? extends K, ? extends V> otherMap)
   {
      if ((mapArr == null) || (mapArr.length == 0))
      {
         // existing map is empty
         mapArr = new Object[otherMap.size() << 1];
         int aIdx = 0;
         for (Entry<? extends K, ? extends V> entry : otherMap.entrySet())
         {
            if ((entry.getKey() == null) || (entry.getValue() == null))
            {
               throw new NullPointerException( "Key or value must not be null.");
            }

            mapArr[aIdx++] = entry.getKey();
            mapArr[aIdx++] = entry.getValue();
         }
      }
      else
      {
         int oldLen = mapArr.length;
         // first increase array size to hold all to put entries as if they have unknown keys
         // reduce after adding all to the required size
         Object[] newMapArr = new Object[oldLen+(otherMap.size() << 1)];
         System.arraycopy(mapArr, 0, newMapArr, 0, oldLen);

         int newIdx = oldLen;
         for (Entry<? extends K, ? extends V> entry : otherMap.entrySet())
         {
            if ((entry.getKey() == null) || (entry.getValue() == null))
            {
               throw new NullPointerException( "Key or value must not be null.");
            }

            int existKeyIdx = findKey(entry.getKey());

            if (existKeyIdx >= 0)
            {
               // existing key
               newMapArr[existKeyIdx+1] = entry.getValue();
            }
            else
            {
               // new key
               newMapArr[newIdx++] = entry.getKey();
               newMapArr[newIdx++] = entry.getValue();
            }
         }

         if (newIdx < newMapArr.length)
         {
            Object[] reducedMapArr = new Object[newIdx];
            System.arraycopy(newMapArr, 0, reducedMapArr, 0, newIdx);
            newMapArr = reducedMapArr;
         }

         mapArr = newMapArr;
      }
   }

   @Override
   public void clear()
   {
      mapArr = null;
   }

   /**
    * Returns a set view of the keys contained in this map.
    *
    * <p>The current implementation does not allow changes to the
    * returned key set (which would have to be reflected in the
    * underlying map.</p>
    */
   @SuppressWarnings("unchecked")
   @Override
   public Set<K> keySet()
   {
      if (isEmpty())
      {
         return Collections.emptySet();
      }

      Set<K> keys = new LinkedHashSet<K>();
      for (int kIdx = 0; kIdx < mapArr.length; kIdx+=2)
      {
         keys.add((K)mapArr[kIdx]);
      }
      return Collections.unmodifiableSet( keys );
   }

   /**
    * Returns a collection of the values contained in this map.
    *
    * <p>The current implementation does not allow changes to the
    * returned collection (which would have to be reflected in the
    * underlying map.</p>
    */
   @SuppressWarnings("unchecked")
   @Override
   public Collection<V> values()
   {
      if (isEmpty())
      {
         return Collections.emptySet();
      }

      List<V> values = new ArrayList<V>(mapArr.length >> 1);
      for (int vIdx = 1; vIdx < mapArr.length; vIdx+=2)
      {
         values.add((V)mapArr[vIdx]);
      }
      return Collections.unmodifiableList( values );
   }

   private class SmallMapEntry implements Entry<K, V>
   {
      private final int keyIdx;

      SmallMapEntry(int keyInMapIdx)
      {
         keyIdx = keyInMapIdx;
      }

      @SuppressWarnings("unchecked")
      @Override
      public K getKey()
      {
         return (K)mapArr[keyIdx];
      }

      @SuppressWarnings("unchecked")
      @Override
      public V getValue()
      {
         return (V)mapArr[keyIdx+1];
      }

      @Override
      public V setValue(V value)
      {
         if (value == null)
         {
            throw new NullPointerException( "Key or value must not be null.");
         }

         V oldValue = getValue();
         mapArr[keyIdx+1] = value;
         return oldValue;
      }

      @Override
      public int hashCode()
      {
         return getKey().hashCode();
      }

      @Override
      public boolean equals(Object obj)
      {
         if (!(obj instanceof SmallMap.SmallMapEntry))
         {
            return false;
         }
         @SuppressWarnings("unchecked")
         SmallMapEntry other = (SmallMapEntry) obj;

         return getKey().equals(other.getKey()) && getValue().equals(other.getValue());
      }
   }

   @Override
   public Set<java.util.Map.Entry<K, V>> entrySet()
   {
      if (isEmpty())
      {
         return Collections.emptySet();
      }

      Set<java.util.Map.Entry<K, V>> entries = new LinkedHashSet<Entry<K, V>>();
      for (int kIdx = 0; kIdx < mapArr.length; kIdx+=2)
      {
         entries.add(new SmallMapEntry(kIdx));
      }
      return Collections.unmodifiableSet( entries );
   }

}
